﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.InteropServices;
using System.Text;

using Util;

namespace Algorithm.Sort
{
    /// <summary>
    /// Bubble sort, also known as sinking sort, 
    /// is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, 
    /// comparing each pair of adjacent items and swapping them if they are in the wrong order.
    /// The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.
    /// The algorithm gets its name from the way smaller elements "bubble" to the top of the list.
    /// Because it only uses comparisons to operate on elements, it is a comparison sort.
    /// Although the algorithm is simple, it is not efficient for sorting large lists;other algorithms are better.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class BubbleSorter <T> : SorterBase <T>
    {
        /// <summary>
        /// In bubble sort process, every pass will finalize an element's position from the end of the list.
        /// </summary>
        /// <param name="elements">The element array to be sortted.</param>
        /// <param name="comparer">The comparer used to determine sort order.</param>
        [AlgorithmVariation]
        public static void BubbleSort(T[] elements, IComparer<T> comparer)
        {
            bool swapped = true;
            int tail = elements.Length - 1;
            int newTail = tail;

            while (swapped)
            {
                swapped = false;

                for (int i = 0; i < tail; i++)
                {
                    if (comparer.Compare(elements[i], elements[i + 1]) > 0)
                    {
                        Swap(elements, i, i + 1);
                        swapped = true;
                        newTail = i;
                    }
                }

                tail = newTail;
            }
        }

        /// <summary>
        /// In sinking sort proecess, every pass will finalize an element's position from the beginning of the list.
        /// </summary>
        /// <param name="elements">The element array to be sortted.</param>
        /// <param name="comparer">The comparer used to determine sort order.</param>
        [AlgorithmVariation]
        public static void SinkSort(T[] elements, IComparer<T> comparer)
        {
            for (int i = 0; i < elements.Length; i++)
            {
                for (int j = i + 1; j < elements.Length; j++)
                {
                    if (comparer.Compare(elements[i], elements[j]) > 0)
                    {
                        Swap(elements, i, j);
                    }
                }
            }
        }
    }
}
